package 五月打卡;

/*
 * @author  YxinMiracle
 * @date  2022-05-05 8:15
 * @Gitee: https://gitee.com/yxinmiracle
 */

import javafx.util.Pair;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

public class 乘积小于K的子数组 {

    public List<List<Integer>> ans = new ArrayList<>();
    public List<Pair<Integer, Integer>> temp = new ArrayList<>(); // 数值 -> 下标
    public int numsLength;
    public Map<Integer, List<Integer>> map = new HashMap<>();

    public int numSubarrayProductLessThanK(int[] nums, int k) {
        this.numsLength = nums.length;
        int result = 0;
        for (int i = 0; i < numsLength; i++) {
            if (!map.containsKey(nums[i])) {
                List<Integer> list = new ArrayList<>();
                list.add(i);
                map.put(nums[i], list);
            } else {
                List<Integer> list = map.get(nums[i]);
                list.add(i);
                map.put(nums[i], list);
            }
        }
        dfs(nums, 0);
        System.out.println(ans);
        for (List<Integer> item : ans) {
            if (item.size() == 0) {
                continue;
            }
            if (item.size() == 1) {
                if (item.get(0) < k) result++;
            }
            if (item.size() > 1) {
                int itemNumResult = 1;
                for (Integer itemNum : item) {
                    itemNumResult *= itemNum;
                    if (itemNumResult >= k) {
                        break;
                    }
                }
                if (itemNumResult < k) {
                    result++;
                }
            }
        }
        return result;
    }

    /**
     * 要是状态由1->0 也就是选择了之后又不选择了，这个就不是子数组
     *
     * @param nums
     * @param cur
     */
    public void dfs(int[] nums, int cur) {
        if (cur >= numsLength) { // 退出
            List<Pair<Integer, Integer>> copy = new ArrayList<>(temp);
            if (copy.size() == 0) return;
            if (copy.size() == 1) {
                List<Integer> list = new ArrayList<>();
                list.add(copy.get(0).getKey());
                ans.add(list);
                return;
            } else {
                // 先判断下标是否连续
                Pair<Integer, Integer> pair1 = copy.get(0);
                Pair<Integer, Integer> pair2 = copy.get(copy.size() - 1);
                int size = copy.size();
                if (pair1.getValue() == 0) {
                    if (pair2.getValue() != size-1) return;
                } else {
                    if (pair2.getValue() - pair1.getValue() != size - 1) return;
                }
                List<Integer> collect = copy.stream().map(Pair::getKey).collect(Collectors.toList());
                ans.add(collect);
                return;
            }

        }
//        System.out.println(cur);
        temp.add(new Pair<>(nums[cur], cur));
        dfs(nums, cur + 1);
        temp.remove(temp.size() - 1);
        dfs(nums, cur + 1);
    }

    public static void main(String[] args) {
        int[] nums = new int[]{10,5,2,6};
        System.out.println(new 乘积小于K的子数组().numSubarrayProductLessThanK(nums, 100));
    }
}



